#include <vector>

using namespace std;

// 三数取中，可以避免数组元素有序时进入最坏情况O(N^2)
int getMidIndex(vector<int> &array, int left, int right)
{
    int midi = (left + right) / 2;
    if(array[left] < array[midi])
    {
        if(array[right] < array[left])
        {
            return left;
        }
        else if(array[midi] > array[right])
        {
            return right;
        }
        else 
        {
            return midi;
        }
    }
    else // array[left] > array[midi]
    {
        if(array[left] < array[right])
        {
            return left;
        }
        else if(array[midi] > array[right])
        {
            return midi;
        }
        else
        {
            return right;
        }
    }
}

int partSort1(vector<int> &array, int left, int right)
{
    int keyi = left;
    while(left < right)
    {
        while(left < right && array[right] >= array[keyi])
        {
            right--;
        }
        while(left < right && array[left] <= array[keyi])
        {
            left++;
        }
        swap(array[left], array[right]);
    }
    swap(array[keyi], array[left]);
    return left;
}

int partSort2(vector<int>& array, int left, int right)
{
     int hole = left, key = array[left];
     while(left < right)
     {
        while(left < right && array[right] >= key)
        {
            right--;
        }
        array[hole] = array[right];
        hole = right;
        while(left < right && array[left] <= key)
        {
            left++;
        }
        array[hole] = array[left];
        hole = left;
     }
     array[hole] = key;
     return hole;
}
int partSort3(vector<int>& array, int left, int right)
{
    int midi = getMidIndex(array, left, right);
    swap(array[left], array[midi]);
    int keyi = left;
    int prev = left, cur = left + 1;
    while(cur <= right)
    {
        if(array[cur] < array[keyi])
        {
            prev++;
            swap(array[prev], array[cur]);
        }
        cur++;
    }
    swap(array[keyi], array[prev]);
    keyi = prev;
    return prev;
}



void QuickSort(vector<int>& array, int begin, int end)
{
    if(begin >= end) return ;
    // int keyi = partSort1(array, begin, end);
    // int keyi = partSort2(array, begin, end);
    int keyi = partSort3(array, begin, end);

    QuickSort(array, begin, keyi - 1);
    QuickSort(array, keyi + 1, end);    
}